'''
https://leetcode.cn/problems/sort-list/description
'''

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def sortList(self, head: [ListNode]) -> [ListNode]:
        # 返回链表中间节点：奇数返回正中心，偶数返回，较左的那一个
        def mid(head):
            if not head or not head.next: return head
            slow, fast = head, head
            while fast.next and fast.next.next:
                slow = slow.next
                fast = fast.next.next
            return slow

        def merge(l1, l2):
            dummy = ListNode()
            cur = dummy
            while l1 and l2:
                if l1.val <= l2.val:
                    cur.next = l1
                    l1 = l1.next
                else:
                    cur.next = l2
                    l2 = l2.next
                cur = cur.next
            cur.next = l1 or l2
            return dummy.next

        def process(head):
            if not head or not head.next: return head
            m = mid(head)
            next = m.next
            m.next = None
            left = process(head)
            right = process(next)
            return merge(left, right)
        return process(head)


print(1 << 6)
print(2 ** 6)